import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 盛最多水的容器
 */
public class TestE {
    public static int func(int[] height) {
        int length = height.length;
        int MAX = 0;
        for (int i = 0; i < length - 1; i++) {
            if(height[i] == 1) {
                MAX = getMaxNum(MAX, (length - 1 - i));
                continue;
            }
            for (int j = length - 1; j > i; j--) {
                int h = getMinNum(height[i],height[j]);
                int l = j - i;
                //getMaxNum(i,j);
                MAX = getMaxNum(MAX,(h*l));
            }
        }
        return MAX;
    }
    public static int getMaxNum(int i, int j) {
        return Math.max(i, j);
    }
    public static int getMinNum(int i,int j) {
        return Math.min(i, j);
    }

    /**
     * 双指针法
     */
    public static int func2(int[] height) {
        int length = height.length;
        int MAX = 0;
        int i = 0,j = length - 1;
        while(i < j) {
            MAX = height[i] < height[j] ?
                    Math.max(MAX,(j - i)*height[i++]) :
                    Math.max(MAX,(j - i)*height[j--]);
        }
        return MAX;
    }

    /**
     * 有效三角形
     */
    public static int func3(int[] nums) {
        int length = nums.length;
        int i = 0;
        int n = 1;
        int j = 2;
        int count = 0;
        while(i <= length - 1) {
            if(isTriangle(nums[i],nums[n],nums[j])) {
                count++;
            }
            i++;
            if(n == length - 1) {
                n = 0;
            }else {
                n++;
            }
            if(j == length - 1) {
                j = 0;
            }else {
                j++;
            }
        }
        return count;
    }
    public static boolean isTriangle(int x,int y,int z) {
        return (x + y > z) && (x + z > y) && (z + y > x);
    }

    /**
     * 有效三角形个数正解
     */
//    static class Solution {
//        public int triangleNumber(int[] nums) {
//            int n = nums.length;
//            Arrays.sort(nums);
//            int ans = 0;
//            for (int i = 0; i < n; ++i) {
//                int k = i;
//                for (int j = i + 1; j < n; ++j) {
//                    while (k + 1 < n && nums[k + 1] < nums[i] + nums[j]) {
//                        ++k;
//                    }
//                    ans += Math.max(k - j, 0);
//                }
//            }
//            return ans;
//        }
//    }

    /**
     * 剑指57 和为s的两个数字
     */
    public static int[] towSum(int[] nums,int target) {
        int max = nums.length - 1;
        int min = 0;
        int[] arr = new int[2];
        if (nums[max] > target) {
            for (int i = 0; i < nums.length; i++) {

                if(nums[i+1] > target) {
                    max = i;
                    break;
                }
            }
        }
        while(min < max) {
            if (nums[min] + nums[max] == target) {
                arr[0] = nums[min];
                arr[1] = nums[max];
                break;
            } else if (nums[min] + nums[max] > target) {
                max--;
            }else if (nums[min] + nums[max] < target) {
                min++;
            }

        }
        return arr;
    }

    /**
     * 环形链表
     */
//    public class Solution {
//        public boolean hasCycle(ListNode head) {
//            if (head == null || head.next == null) {
//                return false;
//            }
//            ListNode slow = head;
//            ListNode fast = head.next;
//            while (slow != fast) {
//                if (fast == null || fast.next == null) {
//                    return false;
//                }
//                slow = slow.next;
//                fast = fast.next.next;
//            }
//            return true;
//        }
//    }

    /**
     * 环形链表2
     */
//    public class Solution {
//        public ListNode detectCycle(ListNode head) {
//            if (head == null) {
//                return null;
//            }
//            ListNode slow = head, fast = head;
//            while (fast != null) {
//                slow = slow.next;
//                if (fast.next != null) {
//                    fast = fast.next.next;
//                } else {
//                    return null;
//                }
//                if (fast == slow) {
//                    ListNode ptr = head;
//                    while (ptr != slow) {
//                        ptr = ptr.next;
//                        slow = slow.next;
//                    }
//                    return ptr;
//                }
//            }
//            return null;
//        }
//    }
//    class MinStack {
//        Stack<Integer> s;
//        Stack<Integer> ms;
//        public MinStack() {
//            s = new Stack<Integer>();
//            ms = new Stack<Integer>();
//            ms.push(Integer.MAX_VALUE);
//        }
//
//        public void push(int val) {
//            s.push(val);
//            ms.push(Math.min(ms.peek(),val));
//        }
//
//        public void pop() {
//            s.pop();
//            ms.pop();
//        }
//
//        public int top() {
//            return s.peek();
//        }
//
//        public int getMin() {
//            return ms.peek();
//        }
//    }
    /**
     * 长度最小的子数组
     */
    public static int minSubArrayLen(int[] nums,int target) {
        if(nums == null) {
            return 0;
        }
        Arrays.sort(nums);
        //1，从头开始遍历，双指针，一个在起始位置start，一个遍历cur
        int count = 0;
        int min = nums.length;
        for (int start = 0; start < nums.length; start++) {
            if(nums[start] > target) {
                break;
            }
            if(nums[start] == target) {
                count = 1;
                break;
            }
            int cur = start + 1;
            int sum = nums[start];
            count = 1;
            while(cur < nums.length) {

                if(sum + nums[cur] == target) {
                    count++;
                    if(count < min) {
                        min = count;
                    }
                    break;
                }else if(sum + nums[cur] < target) {
                    count++;
                    sum += nums[cur];
                    cur++;
                }else if(sum + nums[cur] > target) {
                    break;
                }
            }
        }
        return count;
        //2，当连续数组小于target的时，则让cur++
        //   当连续数组等于target时，则记录当前连续数组的值count
        //   当连续数组大于target时，则让start移动至后一位
        //3，当有下一个连续数组等于target时，让count与之前以为比较
        //4，循环条件为
    }
    /**
     * 三数之和
     * @return
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        //有序排列
        Arrays.sort(nums);

        List<List<Integer>> arr = new ArrayList<>();
        //固定其中一位数，寻找剩余两位数之和与此位数相反
        for (int index = 0;index < nums.length;) {
            if(nums[index] > 0) {
                break;
            }
            int right = nums.length - 1;
            int left = index + 1;
            int target = -nums[index];
            //双指针寻找固定数的相反数
            while(left < right) {
                int sum = nums[left] + nums[right];
                if(sum < target) {
                    left++;
                }else if(sum > target) {
                    right--;
                }else {
                    arr.add(new ArrayList<>(Arrays.asList(nums[index],nums[left],nums[right])));
                    left++;
                    right--;
                    //双指针去重
                    while(left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while(left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }

            }
            //固定数去重
            index++;
            while(index < nums.length && nums[index] == nums[index - 1]) {
                index++;
            }
        }
        return arr;
    }
    public static void main(String[] args) {
          int[] arr = new int[]{-1,0,1,2,-1,-4};
//        System.out.println(func2(arr));
//        System.out.println(func3(arr));
//        for (int x: towSum(arr,9)) {
//            System.out.println(x);
//        }
//        System.out.println(minSubArrayLen(arr,7));
//        int x = -4;
//        int y = -3;
//        int z = y*-1;
//        System.out.println(z+x);
        List<List<Integer>> nums = threeSum(arr);

        for (int i = 0; i < nums.size(); i++) {
            System.out.println(nums.get(i));
        }
    }
}
